package com.algorithm.lesson_12;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 拼接所有字符串产生字典顺序最小的大字符串
 * 
 * @author Administrator
 *
 */
public class ConcatMaxStr {
	// strs=[ "abc"， "de" ]， 可以拼成"abcde"， 也可以拼成"deabc"， 但前者的字典顺序更小， 所以返回"abcde"。
	// strs=["b"， "ba" ]， 可以拼成"bba"， 也可以拼成"bab"， 但后者的字典顺序更小， 所以返回"bab"。

	private static class ConcatComparator implements Comparator<String> {

		@Override
		public int compare(String str1, String str2) {
			// str1str2 < str2str1 str1<str2
			// 如果str1和str2拼接后小于str2和str1拼接的结果则将str1放到str2的前面
			return (str1 + str2).compareTo(str2 + str1);
		}

	}

	public static String getConcatMaxStr(String[] arr) {
		if (arr == null || arr.length == 0) {
			return null;
		}

		Arrays.sort(arr, new ConcatComparator());

		String res = "";

		for (int i = 0; i < arr.length; i++) {
			res += arr[i];
		}

		return res;
	}
}
